// Cracking coding interview
// Write a method to compute all permutations of a string
// 11:33AM-11:53AM

#define _CRTDBG_MAP_ALLOC
#define _CRTDBG_MAP_ALLOC_NEW 
#include <stdlib.h>
#include <crtdbg.h>

#include<string>
#include<iostream>
#include<set>
using namespace std;

#ifdef _DEBUG
   #ifndef DBG_NEW
      #define DBG_NEW new ( _NORMAL_BLOCK , __FILE__ , __LINE__ )
      #define new DBG_NEW
   #endif
#endif  // _DEBUG

void insertPerm(char c, set<string>& strset) {
	set<string> retset;
	set<string>::iterator iter;
	if(strset.empty()) {
		string str;
		strset.insert(str);
	}

	for(iter=strset.begin(); iter!=strset.end(); iter++) {
		for(int i=0; i<=iter->length(); i++) {
			string curstr=iter->substr(0, i)+c; 
			if(i<iter->length()) {
				curstr += iter->substr(i);
			}
			//insert at pos i
			retset.insert(curstr);
		}
	}
	strset=retset;
}

void PermStr(string &str) {
	set<string> strset;
	for(int i=0; i<str.size(); i++) {
		insertPerm(str[i], strset);
	}
	set<string>::iterator iter;
	for(iter=strset.begin(); iter!=strset.end(); iter++) {
		cout<<*iter<<endl;
	}
}

void test() {
	string str="abcefghijklmnopajdfalskdjfldsjaflskdjfsajfls;jfdsjflsa;jfklsajflsjf;sdkjf";
	//char *a=new char[5];
}

int main(int argc, char *argv[]) {
	//_CrtSetDbgFlag ( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF );
	_CrtSetReportMode( _CRT_ERROR, _CRTDBG_MODE_DEBUG );
	//string str="abcefghijklmnopajdfalskdjfldsjaflskdjfsajfls;jfdsjflsa;jfklsajflsjf;sdkjf";
	//string str="abc";
	//PermStr(str);
	_CrtMemState s1, s2, s3;
	_CrtMemCheckpoint( &s1 );
	char *a=new char[5];
	_CrtMemCheckpoint( &s2 );
	if ( _CrtMemDifference( &s3, &s1, &s2) )
		_CrtMemDumpStatistics( &s3 );
	//str.erase(str.begin(), str.end());
	//str.clear();
	//_CrtDumpMemoryLeaks();
	return 0;
}